Computation with sparse matrices is at the heart of a wide range of applications in computational science and modeling. Many sparse matrix algorithms use an active column (or active row, or group of active columns or rows) in which a major part of the numerical computation takes place. The requirements for representing and manipulating the active column typically differ from the requirements for an entire sparse matrix in two ways:
More flexible and efficient access is required to the active column than to the whole matrix. For example, it may be necessary to sequence through the nonzero elements of the active column, and also to access individual elements at random. PA1 The active column is a relatively small part of the data used in the computation, so the requirement to conserve space in its representation is not as stringent as it is for the larger data structures.
A structure called the sparse accumulator, or SPA, has been used to represent an active column by several workers, including Gilbert, Moler, and Schreiber, "Sparse Matrices in Matlab: Design and Implementation", SIAM Journal on Matrix Analysis and Applications, 13:333-356, 1992. The SPA permits random access to individual elements, and sequencing through individual elements, both in constant time per element accessed. In the sequencing operation, the nonzero elements cannot be accessed in numerical order by index; and the nonzero structure of the SPA cannot be altered during the sequencing operation.